#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int integerReplacement(long n);

int main()
{
	return 0;
}

int integerReplacement(long n)
{
	int times = 0;
	while (n > 1) {
		if (n == 3) return times + 2;
		if (n & 1) {
			if ((n & 3) == 1) n = n - 1;
			else n = n + 1;
		} else n >>= 1;
		times++;
	}
	return times;
}
